package easy

import (
	"math"
	"unicode"
)

/*
时间复杂度:O(N+L+M⋅∣Σ∣) N 是字符串licensePlate 的长度，L 是words 中的所有字符串的长度之和，M是words 数组的长度，∣Σ∣ 为字符集合的大小，
			本题中有 26 个英文字母，即∣Σ∣=26

空间复杂度:O(∣Σ∣)
*/

func shortestCompletingWord(licensePlate string, words []string) string {
	var arr [26]int
	for _, ch := range licensePlate {
		// 判读是否是大写或小写字母
		if unicode.IsLetter(ch) {
			arr[unicode.ToLower(ch)-'a']++
		}
	}

	count := math.MaxInt32
	ans := ""
	for _, word := range words {
		var t [26]int
		for _, ch := range word {
			t[ch-'a']++
		}
		i := 0
		for ; i < 26; i++ {
			if t[i] < arr[i] {
				break
			}
		}
		if i == 26 {
			if count > len(word) {
				count = len(word)
				ans = word
			}
		}
	}
	return ans
}
